In electronic systems employing devices that must communicate with each other in order to accomplish tasks, it is important to ensure that packets are received at the intended destination device in a timely fashion. In systems employing interconnected integrated circuits, there may be multiple communications pathways that may be coupled together within the system as well as to the external environment. Thus, multiple possible communications pathways exist between the source and destination devices. Choosing one path over another for communications at a given moment may be inconsequential in systems where communication speed and efficiency is not a paramount concern. However, in systems having many such pathways and where communication speed needs to be optimized, communications pathway choice needs to be carefully considered.
In systems having just a few choices of possible communications pathways, it may be relatively simple to choose the communications pathway to use that minimizes the time a packet is in transition between the source and destination devices. However, in larger systems employing many devices and having many possible communications pathways between devices, it is necessary to approach the choice of a pathway more carefully. Further, having a systematic method for choosing an optimum pathway that minimizes transit time between source and destination increases system efficiency.
In a system having multiple intersecting communications pathways, a signal being routed from a source device to a destination device may have several possible choices of pathways at each intersection. For example, in a rectangular layout where a signal is going from the lower right corner to the upper left corner, there are likely to be many possible choices for routing a signal at each intersection. In addition to considering latency when routing a signal, other factors are considered, such as the possibility that a portion of a pathway may fail, thus requiring the system to reroute the signal.